Optimal Interconnection Trees in the Plane by Marcus Brazil & Martin Zachariasen

Author:Marcus Brazil & Martin Zachariasen
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

Proof

Let G = (V, E) be a planar graph with no vertex degree exceeding 4, and let k be a positive integer. We construct a terminal set N in the plane for which a rectilinear Steiner tree T of length at most L exists if and only if G has a connected vertex cover C of size at most k. (The length bound L is specified later.)

The first step in the construction of N is to embed the planar graph G = (V, E) in the plane. Let n =  | V | and m =  | E | . Define the integer . Consider a grid of squares in the plane, where each grid point has integer coordinates that are multiples of . Map each vertex in V to distinct grid points, and each edge in E to non-intersecting grid paths (Fig. 3.21). Such a grid embedding can be obtained in O(n) time – and in such a way that the rectangular area covered has at most O(n 2) grid squares [359].

Fig. 3.21Embedding of planar graph (top) in a grid of squares (bottom). The vertex set forms a connected vertex cover of size 4

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.